/*
 *KMP算法
 * */
#include <cstdio>
#include <cstring>

void getNext(char *str, int next[]);
int indexStr(char *m_str, char *p_str, int next[]);

int main() {
  char s_str[] =
      "rrffgggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"
      "gggggggggggggggggg好的ggggggggggggggggggggggggggggggggggaahaaggggggggggg"
      "gggg"
      "ggggg"
      "gggggggggggggggggggggggggggaaaa#faahaafhj"; // 主串
  char p_str[] = "好的";                           // 模式串
  char *po_str = p_str;
  int next[strlen(p_str)];

  getNext(p_str, next);
  int index = indexStr(s_str, p_str, next);

  // 输出前缀表
  printf("\n+++++++++++++++++++++++++\n");
  printf("pstr:");
  for (int i = 0; i < strlen(p_str); i++) {
    printf(" %c ", *(po_str++));
  }
  printf("\n");
  printf("next:");
  for (int i = 0; i < strlen(p_str); i++) {
    printf(" %d ", next[i]);
  }
  printf("\n+++++++++++++++++++++++++\n");
  printf("index:%d", index);
  return 0;
}
int indexStr(char *m_str, char *p_str, int next[]) {
  /*
   *计算匹配成功的索引号
   * */
  int m_len = strlen(m_str);
  int p_len = strlen(p_str);
  int i = 0;
  int j = 0;
  while (i < m_len && j < p_len) {
    if (m_str[i] == p_str[j]) {
      i++;
      j++;
    } else {
      if (j > 0) {
        j = next[j - 1];
      } else {
        i++;
      }
    }
  }
  if (j == p_len) {
    return i - p_len;

  } else
    return -1;
}

void getNext(char *str, int next[]) {
  /* 获得前缀数组
   * str: 匹配字符串
   * next:前缀数组
   * */

  int i;     // 后缀末位指针
  int j = 0; // 前缀末位指针
  next[0] = 0;
  int str_len = int(strlen(str));
  for (i = 1; i < str_len; i++) {
    // 情况1:后缀指针和前缀指针相等并且前缀不是第0位
    while (j > 0 && str[i] != str[j]) {
      j = next[j - 1];
    }
    // 情况2:相等时
    if (str[i] == str[j]) {
      j++;
    }
    // 最后赋值
    next[i] = j;
  }
}
